﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using GraphLib;

using System.Diagnostics;

namespace WindowsFormsApplication2
{
    /// <summary>
    /// Класс-библиотека, содержащий в себе все алгоритмы нахождения кратчайших путей в графе
    /// </summary>
    public class Algorithms
    {
        /// <summary>
        /// Задача о кратчайшей цепи (Дейкстра)
        /// </summary>
        /// <param name="graph">Граф</param>
        /// <param name="pointSource">Точка источник</param>
        /// <param name="pointRunoff">Точка сток</param>
        /// <returns>Кратчайший путь в виде листа точек</returns>
        public static List<GraphPoint> Algorithm1_Go(Graph graph, GraphPoint pointSource, GraphPoint pointRunoff)
        {
            var listPaths = new List<List<GraphPoint>>();

            var sourceList = new List<GraphPoint>();
            sourceList.Add(pointSource);
            listPaths.Add(sourceList);

            bool isEnd = false;

            while (!isEnd)
            {
                int currentCnt = listPaths.Count;
                for (int i = 0; i < currentCnt; i++)
                {
                    if (listPaths[i].Count > 0)
                    {
                        GraphPoint lastPoint = listPaths[i][listPaths[i].Count - 1];
                        if (lastPoint != pointRunoff)
                        {
                            var nearby = graph.GetNearbyPoints(lastPoint);
                            CheckPaths(listPaths[i], nearby);
                            if (nearby != null)
                                foreach (var nearPoint in nearby)
                                {
                                    var tempPath = new List<GraphPoint>();
                                    tempPath.AddRange(listPaths[i]);
                                    tempPath.Add(nearPoint);
                                    listPaths.Add(tempPath);
                                }
                            listPaths.RemoveAt(i);
                            i--;
                            currentCnt--;
                        }
                    }
                }

                isEnd = true;
                foreach (var path in listPaths)
                {
                    if (path[path.Count - 1] != pointRunoff)
                        isEnd = false;
                }
            }

            List<GraphPoint> shortestPath = null;
            int minPathWeight = 0;
            bool isFirst = true;
            foreach (var path in listPaths)
            {
                int currentWeight = CountPathWeight(graph, path);
                if (isFirst)
                {
                    minPathWeight = currentWeight;
                    shortestPath = path;
                    isFirst = false;
                }
                if (minPathWeight > currentWeight)
                {
                    minPathWeight = currentWeight;
                    shortestPath = path;
                }
            }

            return shortestPath;
        }

        public static List<List<GraphPoint>> Algorithm2_Go(Graph graph)
        {
            var listPaths = new List<List<GraphPoint>>();

            foreach (var point1 in graph.Points)
            {
                foreach (var point2 in graph.Points)
                {
                    if (point2 != point1)
                    {
                        var tempList = Algorithm1_Go(graph, point1, point2);
                        listPaths.Add(tempList);
                    }
                }
            }

            return listPaths;
        }

        public static int Algorithm3_Go(Graph graph, GraphPoint pointSource, GraphPoint pointRunoff)
        {
            int maxFlow = 0;
            Graph tempGraph = new Graph();
            foreach (var item in graph.Points)
            {
                GraphPoint tempGPoint = new GraphPoint();
                tempGPoint.X = item.X;
                tempGPoint.Y = item.Y;
                tempGPoint.Name = item.Name;

                tempGraph.Points.Add(tempGPoint);
            }

            foreach (var item in graph.Links)
            {
                GraphLink tempGLink = new GraphLink();
                tempGLink.P1 = item.P1;
                tempGLink.P2 = item.P2;
                tempGLink.Weight = item.Weight;
                tempGLink.Ld = item.Ld;

                tempGraph.Links.Add(tempGLink);
            }

            bool isEnd = false;

            while (!isEnd)
            {
                List<GraphPoint> tempPath = Algorithm1_Go(tempGraph, pointSource, pointRunoff);
                if (tempPath == null)
                    isEnd = true;
                else
                {
                    int tempFlow = GetPathMaxFlow(tempGraph, tempPath);
                    for (int i = 0; i < tempPath.Count - 1; i++)
                    {
                        GraphLink tempGLink = tempGraph.FindFirstLink(tempPath[i], tempPath[i + 1]);
                        if (tempGLink.Weight > tempFlow)
                        {
                            tempGLink.Weight -= tempFlow;
                        }
                        else
                        {
                            for (int j = 0; j < tempGraph.Links.Count; j++)
                            {
                                if (tempGraph.Links[j] == tempGLink)
                                {
                                    tempGraph.Links.RemoveAt(j);
                                    j--;
                                }
                            }
                        }
                    }
                    maxFlow += tempFlow;
                }
            }

            return maxFlow;
        }

        public static List<GraphLink> Algorithm4_Go(Graph graph)
        {
            var maxFlows = new List<GraphLink>();

            foreach (var point1 in graph.Points)
            {
                foreach (var point2 in graph.Points)
                {
                    if (point2 != point1)
                    {
                        GraphLink tempGLink = new GraphLink();
                        tempGLink.Weight = Algorithm3_Go(graph, point1, point2);
                        tempGLink.P1 = point1;
                        tempGLink.P2 = point2;
                        tempGLink.Ld = LinkDirection.LdStraight;
                        maxFlows.Add(tempGLink);
                    }
                }
            }

            return maxFlows;
        }

        private static void CheckPaths(List<GraphPoint> path, List<GraphPoint> nearby)
        {
            if (nearby == null)
                return;
            foreach (var nearPoint in nearby)
            {
                foreach (var pathPoint in path)
                {
                    if (nearPoint == pathPoint)
                        nearby.Remove(nearPoint);
                }
            }

            return;
        }

        private static int CountPathWeight(Graph graph, List<GraphPoint> path)
        {
            int weight = 0;

            if (path.Count > 1)
            {
                for (int i = 0; i < path.Count - 1; i++ )
                {
                    GraphLink gLink = graph.FindFirstLink(path[i], path[i + 1]);
                    if (gLink != null)
                    { 
                        weight +=gLink.Weight;
                    }
                }
            }
            return weight;
        }

        private static int GetPathMaxFlow(Graph graph, List<GraphPoint> path)
        {
            int flow = 0;
            if (path.Count > 1)
            {
                flow = graph.FindFirstLink(path[0], path[1]).Weight;
                for (int i = 0; i < path.Count - 1; i++)
                {
                    if (flow > graph.FindFirstLink(path[i], path[i + 1]).Weight)
                    {
                        flow = graph.FindFirstLink(path[i], path[i + 1]).Weight;
                    }
                }
            }

            return flow;
        }

    }
}
